// https://www.lintcode.com/problem/wood-cut/description

class Solution {
public:
    /**
     * @param L: Given n pieces of wood with length L[i]
     * @param k: An integer
     * @return: The maximum length of the small pieces
     */
    int getAns(vector<int> &L, int length) {
        int ans = 0;
        for (const auto& l: L) {
            ans += l / length;
        }
        return ans;
    }
    int woodCut(vector<int> &L, int k) {
        if (L.empty()) {  //!!!
            return 0; 
        }
        int low = 1;
        // int high = *max_element(L);
        int high = *max_element(L.begin(), L.end());
        while (low + 1 < high) {
            int mid = (high - low) / 2 + low;
            if (getAns(L, mid) >= k) {
                low = mid;
            } else {
                high = mid;
            }
        }
        if (getAns(L, high) >= k) {
            return high;
        // } else {
        //     return low;
        // }
        } else if (getAns(L, low) >= k) {
            return low;
        } else {
            return 0;
        }
    }
};